package com.company.algo.niuke;

import com.company.algo.pojo.TreeNode;

/**【剑指offer原题，看了又不会了】--字节
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 若root为p,q的公共祖先，只有三种情况
 * 1. p和q在root的子树中，且分布在root的异侧
 * 2. p=root,且q在root的左或右子树中
 * 3. q=root,且p在root的左或右子树中
 * 所以先遍历左子树，如果找到了p或q，将之返回记为left，找不到就返回Null
 * 然后遍历右子树，如果找到p或q，将之返回记为right，找不到就返回Null
 * 最后判断left和right是否为null，
 * 若left==null,则公共祖先一定是right(左子树中没有找到目标节点)
 * 若right==null,则公共祖先一定是left(右子树中没有找到目标节点)
 * 若全不为null，则返回root(异侧)
 */
public class LowestCommonAncestor {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        if (root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}
